#include "Parser.h"
#include "Scanner.h"
#include <fstream>
#include <iostream>
#include <sstream>

//Constructor - Grammar-rules, and takes input file for comparison
Parser::Parser(map<string, vector<string> > rules_, string input_file_, vector<
		string> listOfTokens_, vector<string> listOfNTs_, string start) {
	rules = rules_;
	input_file = input_file_;
	listOfTokens = listOfTokens_;
	listOfNTs = listOfNTs_;
	start_state = start;
}

Parser::~Parser() {

}

//Automate process to parse input vs table
void Parser::parse() {
	cout << endl << endl << "Removing Common Prefix" << endl << endl;
	removeLeftFactoring();

	cout << endl << "Removing Left Recursion" << endl << endl;
	removeLeftRecursion();

	cout << endl << endl;
	printGrammar();

	createFirstSets();
	createFollowSets();
	createParseTable();
	checkInput();
}

void Parser::removeLeftFactoring() {

	make3DData();

	ThreeDMapType::iterator endy = TDData.end();
	for (ThreeDMapType::iterator it = TDData.begin(); it != endy; ++it) {

		//Indexing into map to get current production rule
		vector<vector<string> > vec = it->second;
		string rule_name = it->first;

		//Detect for Common Prefix
		for (int i = 0; i < vec.size(); ++i) {
			for (int j = i + 1; j < vec.size(); ++j) {
				if (vec[i][0] == vec[j][0]) { //If Common Prefix exists then handle it
					vector<vector<string> > replace =
							vector<vector<string> > ();
					string new_name;
					fixLeftFactoring(vec, replace, vec[i][0], new_name);
					TDData[new_name] = replace;
					TDData[it->first] = vec;
				}
			}
		}
	}
	//Print out after operations
	print3DMap(TDData);
}

void Parser::fixLeftFactoring(vector<vector<string> > &original, vector<vector<
		string> > &new_rule, string common, string &new_name) {
	cout << "Commons! " << common << endl;
	new_name = "new_" + common;

	int inc_index = 0;

	//Finding target indexes that I have common prefix
	vector<int> targets;

	for (int i = 0; i < original.size(); ++i) {
		if (original[i][0] == common) {
			cout << "Index " << i << endl;
			targets.push_back(i);
		}
	}

	//Use Target Indexes to build new rule
	//Start building the new rule.
	vector<vector<string> > newstuff();
	new_rule.push_back(vector<string> ());

	for (int i = 0; i < targets.size(); ++i) {

		//If common thing was only thing then replace to empty string
		if (original[targets[i]].size() == 1) {
			new_rule[inc_index].push_back("ε");
			cout << "S: " << i << " " << "ε" << endl;
		}

		//Add non-singular rules to new rules
		for (int j = 1; j < original[targets[i]].size(); ++j) {
			cout << "S: " << i << " " << original[targets[i]][j] << endl;
			new_rule[inc_index].push_back(original[targets[i]][j]);
		}
		new_rule.push_back(vector<string> ());
		++inc_index;
	}
	//clean up extra
	new_rule.pop_back();

	//Fix the original rule
	int inc_targ = 0;
	int inc_new = 0;

	vector<vector<string> > newbie;
	for (int i = 0; i < original.size(); ++i) {

		//If common prefix then we ignore -> handled in above code
		if (targets[inc_targ] == i) {
			++inc_targ;
			continue;
		}

		//Add new entry and add everything that's Not common
		newbie.push_back(vector<string> ());
		for (int j = 0; j < original[i].size(); ++j) {
			newbie[inc_new].push_back(original[i][j]);
		}

		++inc_new;
		cout << "Index: " << i << endl;
	}
	newbie.push_back(vector<string> ());
	newbie[inc_new].push_back(new_name);

	//Switch original to updated version
	original = newbie;
}

//Method that handles left recusion if detected my removeLeftRecursion
void Parser::handleLeftRecursion(string main_rule, vector<string> &o_rule,
		vector<string> &n_rule, vector<int> targs) {

	vector<string> a = vector<string> ();
	vector<string> aprime = vector<string> ();

	bool mode = false;
	int index = 0;

	vector<string> orig_rule = o_rule;
	vector<string> new_rule = n_rule;

	//Adds rules to both new rules based on mode
	for (int i = 0; i < orig_rule.size(); ++i) {
		if (targs[index] == i) {
			mode = true;
			++i;
			++index;
		} else if (orig_rule[i] == "|") {
			mode = false;
		}

		if (!mode) {
			if (!(a.size() == 0 && orig_rule[i] == "|"))
				a.push_back(orig_rule[i]);
		} else {
			if (!(aprime.size() == 0 && orig_rule[i] == "|"))
				aprime.push_back(orig_rule[i]);
		}
	}

	//Cleans up trailing | symbols
	if (a[a.size() - 1] == "|")
		a.pop_back();

	if (aprime[aprime.size() - 1] == "|")
		aprime.pop_back();

	vector<string> *newa = new vector<string> ();
	for (int i = 0; i < a.size() - 1; ++i) {
		newa->push_back(a[i]);
		if (a[i + 1] == "|")
			newa->push_back(main_rule + "'");
	}

	newa->push_back(a[a.size() - 1]);
	newa->push_back(main_rule + "'");
	o_rule = *newa;

	//Add on rules, but also adds on the new recursive rule
	newa = new vector<string> ();
	for (int i = 0; i < aprime.size() - 1; ++i) {
		newa->push_back(aprime[i]);
		if (aprime[i + 1] == "|")
			newa->push_back(main_rule + "'");
	}

	newa->push_back(aprime[aprime.size() - 1]);
	newa->push_back(main_rule + "'");

	//Add on empty string state
	newa->push_back("|");
	newa->push_back("ε");

	n_rule = *newa;
}

//Main method for Left Recursion Removal.
//It detects left recursion and calls helper method to fix it
void Parser::removeLeftRecursion() {

	MapType data = rules;

	MapType::const_iterator end = data.end();
	for (MapType::const_iterator it = data.begin(); it != end; ++it) {
		string main_rule = it->first;
		vector<string> vec = it->second;

		vector<int> targs = vector<int> ();

		//Detect if rule has left recursion
		bool before = false;
		for (int i = 0; i < vec.size(); ++i) {
			if (vec[i] == "|")
				before = false;
			else if (main_rule == vec[i] && !before) {
				targs.push_back(i);
				cout << "Left Recursion " << main_rule << endl;
				vector<string> new_rule = vector<string> ();
				handleLeftRecursion(main_rule, vec, new_rule, targs);
				rules[main_rule] = vec;
				rules[main_rule + "'"] = new_rule;
				listOfNTs.push_back(main_rule + "'");
			} else {
				before = true;
			}
		}
	}
}

void Parser::printGrammar() {
	typedef map<string, vector<string> > MapType;
	MapType data = rules;
	MapType::const_iterator end = data.end();
	for (MapType::const_iterator it = data.begin(); it != end; ++it) {
		string main_rule = it->first;
		vector<string> vec = it->second;

		cout << main_rule << " -> ";
		for (int i = 0; i < vec.size(); ++i) {
			cout << vec[i] << " ";
		}
		cout << endl;
	}
}

void Parser::printToFile(parsetable &table) {
	ofstream out(output);
	if (!out) {
		cout << "Cannot open file.\n";

	}
	//printing out the top line of tokens
	out << ",";
	for (int i = 0; i < listOfTokens.size(); i++)
		out << listOfTokens[i] + ",";
	out << endl;
	//printing out everything else.
	for (parsetable::iterator it = table.begin(); it != table.end(); it++) {
		string nonterminal = it->first;
		MapType otherHash = it->second;
		out << nonterminal.c_str();
		out << ",";
		for (int i = 0; i < listOfTokens.size(); i++) {
			string terminal = listOfTokens[i];
			vector<string> listOfRules = otherHash[terminal];
			for (int i = 0; i < listOfRules.size(); i++) {
				if (i != 0)
					out << " | ";
				out << listOfRules[i].c_str();
			}
			out << ",";
		}
		out << endl;
	}
	out.close();
}
void Parser::printParseTable(parsetable &table) {

	for (parsetable::iterator it = table.begin(); it != table.end(); it++) {
		string nonterminal = it->first;
		MapType otherHash = it->second;
		printf("%s", nonterminal.c_str());
		for (MapType::iterator it2 = otherHash.begin(); it2 != otherHash.end(); it2++) {
			string terminal = it2->first;
			vector<string> listOfRules = it2->second;
			printf("%s : ", terminal.c_str());
			for (int i = 0; i < listOfRules.size(); i++) {
				printf("%s", listOfRules[i].c_str());
			}
			printf(".");
		}
		printf("\n");
	}
	printf("\n");
}

//Decodes the rule in parsing table
void Parser::decode(vector<string> &stack, string rule, string input) {

	//Gets the string rule and adds it to the vector. String of strings -> vector of strings
	istringstream* ss = new istringstream(rule);
	string temp = "";
	*ss >> temp;
	*ss >> temp;
	*ss >> temp;

	vector<string> new_stuff = vector<string> ();
	while (ss->good()) {
		new_stuff.push_back(temp);
		*ss >> temp;
	}
	for (int i = new_stuff.size() - 1; i >= 0; --i)
		stack.push_back(new_stuff[i]);

}

void Parser::checkInput() {

	//Open up Scanner for file reading
	Scanner* scan = new Scanner();
	char* file = (char*) input_file.c_str();

	//Adding the $ token to the stack
	vector<string> stack = vector<string> ();
	stack.push_back("$");
	stack.push_back(start_state);

	bool succ_parse = false;

	scan->readFile(file);
	string input = scan->next();
	int count = 0;
	while (isTerminal(input)) {
		count++;
		string rule_lookup = stack[stack.size() - 1];

		//Should never look for $ in table -> Error
		if (rule_lookup == "$") {
			cout << "Parse result: Fail first one" << endl;
			return;
		}

		string new_elem = getTableContents(rule_lookup, input);
		cout << "Look up in table: " << rule_lookup << " Input token:" << input;

		//Pop what we looked up off the stack
		stack.pop_back();

		//The rule coming back from table is one string, decode parses it
		decode(stack, new_elem, input);

		//Remove all the terminal characters

		for (int i = stack.size() - 1; i > 0; --i)
			if (isTerminal(stack[i])) {
				stack.erase(stack.begin() + i);
			}

		//Print out stack
		cout << endl;
		cout << "Printing Stack" << endl;
		for (int i = stack.size() - 1; i >= 0; --i)
			cout << stack[i] << endl;

		cout << endl;

		input = scan->next();
		cout << input << endl;
	}

	cout << stack.size() << endl;
	//Check if good parse!
	if (stack.size() == 1 && stack[0] == "$")
		succ_parse = true;

	if (succ_parse)
		cout << "Parse result: Success" << endl;
	else
		cout << "Parse result: Fail LOL" << endl;

}

//Looks up into the table and returns rule
string Parser::getTableContents(string rule, string token) {
	MapType temp = vidtable[rule];
	if (temp[token].size() == 0)
		return "";
	return temp[token][0];
}

//Creates parse table with first and follow sets
void Parser::createParseTable() {
	listOfTokens.push_back("$");
	/*
	 repeat the following two steps for each NT A and production choice A -> α
	 1) For each token a in First(α), Add A-> α to teh entry M[A,a]
	 2) If eps is in First(α), for each element a of Follow(A) (token or $), add A-> α to M[A,a]
	 */

	for (int i = 0; i < listOfNTs.size(); i++) {
		for (int j = 0; j < listOfTokens.size(); j++) {
			vidtable[listOfNTs[i]][listOfTokens[j]] = vector<string> ();
		}
	}

	cout << endl << "Printing table" << endl;

	for (ThreeDMapType::iterator it = TDData.begin(); it != TDData.end(); it++) {
		// it = rule
		string main_rule = it->first;
		vector<vector<string> > vec = it->second;
		vector<string> Firstalpha;
		string a;
		for (vector<vector<string> >::iterator it2 = vec.begin(); it2
				< vec.end(); it2++) {
			//it2 = vector<string>  each production
			vector<string> alpha = (*it2);
			string alphaknot = alpha.at(0);
			if (isTerminal(alphaknot)) { //if terminal, just use that
				Firstalpha.clear();
				Firstalpha.push_back(alphaknot);
			} else {
				Firstalpha = FirstSet[alphaknot]; //if not terminal, get its First Set
			}
			a = alphaknot;
			for (int i = 0; i < Firstalpha.size(); i++) {
				if (isTerminal(Firstalpha[i])) {
					a = Firstalpha[i];
					//add A-> alpha to M[A,a]
					string temp; //string constructing to be inserted
					temp.append(main_rule);
					temp.append(" -> ");
					for (int i = 0; i < alpha.size(); i++)
						temp.append(alpha[i] + " ");
					if (!checkIfContains(vidtable[main_rule][a], temp)) { //checking for possible duplication
						vidtable[main_rule][a].push_back(temp.c_str());
						printf("added %s to M[%s,%s]\n", temp.c_str(),
								main_rule.c_str(), a.c_str());
					}
				}
			}
			if (checkForEpsilon(Firstalpha)) { //as per the algorithm
				for (vector<string>::iterator it3 =
						FollowSet[main_rule].begin(); it3
						< FollowSet[main_rule].end(); it3++) {
					if (isTerminal(*it3) | (*it3).compare("$") == 0) {
						a = *it3;
						//add A-> alpha to M[A,a]
						string temp;
						temp.append(main_rule);
						temp.append(" -> ");
						for (int i = 0; i < alpha.size(); i++)
							temp.append(alpha[i] + " ");
						if (!checkIfContains(vidtable[main_rule][a], temp)) { //same as above, just repeat for many
							vidtable[main_rule][a].push_back(temp.c_str());
							printf("added %s to M[%s,%s]\n", temp.c_str(),
									main_rule.c_str(), a.c_str());
						}
					}
				}
			}
		} //end for
	}
	printToFile(vidtable);
}

//Create first sets
void Parser::createFirstSets() {
	/*for each production rule X -> X1X2...Xn do
	 k:=1;
	 while k<=n do
	 First(A) = First(A) U (First(Xk)-{eps})
	 if eps is not in First(Xk) then break;
	 k := k+1;
	 if ( k>n) then First(A) = First(A) U {eps}
	 */

	MapType data = rules;
	printf("\n");

	make3DData();

	bool hasChanged = true;
	while (hasChanged) {
		hasChanged = false;
		for (ThreeDMapType::iterator it = TDData.begin(); it != TDData.end(); it++) { //for each rule
			string main_rule = it->first;
			vector<vector<string> > vecs = it->second;

			for (vector<vector<string> >::iterator it2 = vecs.begin(); it2
					< vecs.end(); it2++) { //for each production

				int k = 1;
				int n = (*it2).size();
				while (k <= n) { //for each element in the production
					string xK = (*it2)[k - 1];
					vector<string> FirstxK;
					if (isTerminal(xK)) {
						FirstxK.clear();
						FirstxK.push_back(xK);
					} else
						// if not a terminal
						FirstxK = FirstSet[xK];

					//need to erase epsilon
					eraseEpsilon(FirstxK); //
					eliminateSpaces(FirstxK);
					for (int i = 0; i < FirstxK.size(); i++) { //adding First(Xk)-eps to First(main_rule)
						if (!checkIfContains(FirstSet[main_rule], FirstxK[i])) {
							FirstSet[main_rule].push_back(FirstxK[i]);
							hasChanged = true;
						}
					}

					if (isTerminal(xK)) {
						FirstxK.clear();
						FirstxK.push_back(xK);
					} else
						FirstxK = FirstSet[xK];

					if (!(checkForEpsilon(FirstxK))) {
						break;
					}
					k++;
				}
				if (k > n) { //other condition which must be checked for
					if (!checkIfContains(FirstSet[main_rule], "ε")) {
						FirstSet[main_rule].push_back("ε");
						eliminateSpaces(FirstSet[main_rule]);
						hasChanged = true;
					}
				}
			}
		}
	}
	cout << "First Set" << endl;
	print2DMap(FirstSet);
}

bool Parser::checkIfContains(vector<string> &firstSet, string toCheck) {
	for (vector<string>::iterator it = firstSet.begin(); it < firstSet.end(); it++) {
		if ((*it).compare(toCheck) == 0)
			return true;
	}
	return false;
}

bool Parser::checkForEpsilon(vector<string> &vec) {
	for (vector<string>::iterator it = vec.begin(); it < vec.end(); it++) { //since 2d array, we need to check another dimension
		if ((*it).compare("ε") == 0)
			return true;
	}
	return false;
}

void Parser::eraseEpsilon(vector<string> &vec) {

	for (vector<string>::iterator it = vec.begin(); it //for each element in the production, erasing eps.
			< vec.end(); it++) { //[A] [B] [C]
		string tstring(*it);

		if (tstring.compare("ε") == 0) {
			//printf("string matched: %s \n", tstring.c_str());
			it = vec.erase(it);

		}

	}
}

void Parser::createFollowSets() {

	/*Follow(start-symbol):= {$}
	 for all nonterminals != start-symbol do Follow(A):={};

	 while there are any changes to any Follow sets do
	 for each production do
	 for each Xi that is a nonterminal do
	 add First(Xi..Xn) - eps to Follow(Xi)
	 if end condition
	 if eps is in First(Xi+1...Xn) then
	 add Follow(A) to Follow(Xi)
	 */

	bool hasChanged = true;
	while (hasChanged) {
		hasChanged = false;
		for (ThreeDMapType::iterator it = TDData.begin(); it != TDData.end(); it++) { //for each rule
			string main_rule = it->first;
			vector<vector<string> > vecs = it->second;
			for (vector<vector<string> >::iterator it2 = vecs.begin(); it2
					< vecs.end(); it2++) { //for each production

				//it2 = vector<string>, A->B|C|D
				for (vector<string>::iterator it3 = (*it2).begin(); it3
						< (*it2).end(); it3++) {
					//it3 = string, = B

					if (!(isTerminal(*it3))) {
						vector<string> FirstXip1; //Will hold First(Xi+..)

						if (it3 + 1 == (*it2).end()) {//condition for checking end
							FirstXip1.push_back("ε");
						} else {
							// if the next thing is a terminal or not
							if (isTerminal(*(it3 + 1)))
								FirstXip1.push_back(*(it3 + 1));
							else
								FirstXip1 = FirstSet[*(it3 + 1)];
						}
						//adding FirstXip1 to Follow(Xi)
						for (int i = 0; i < FirstXip1.size(); i++) {
							if (FirstXip1[i].compare("ε") != 0) //making sure we're not adding an epsilon
								if (!checkIfContains(FollowSet[*it3],
										FirstXip1[i])) { //making sure we're not adding the same thing again
									FollowSet[*it3].push_back(FirstXip1[i]);
									hasChanged = true;
								}
						}
						if (checkForEpsilon(FirstXip1)) //this is the epsilon case
							for (int i = 0; i < FollowSet[main_rule].size(); i++) {
								if (!checkIfContains(FollowSet[*it3],
										FollowSet[main_rule][i])) {
									FollowSet[*it3].push_back(
											FollowSet[main_rule][i]);
									hasChanged = true;
								}
							}
					} // end if nonterminal
				}// end for each string

			} //end each production
		}
	}
	cout << "Follow Set" << endl;
	print2DMap(FollowSet);
}
void Parser::make3DData() {
	MapType data = rules;
	// this is creating the new 3d array;
	MapType::const_iterator end = data.end();
	for (MapType::const_iterator it = data.begin(); it != end; ++it) {

		string main_rule = it->first; //grabbing the rule
		vector<string> vec = it->second; //grabbing the vector of vectors that corresponds to the rule
		FirstSet[main_rule] = vector<string> (); //creating the nonterminals to empty list.
		FollowSet[main_rule] = vector<string> (); //initializing the FollowSet
		if (main_rule.compare(start_state) == 0) // for the follow set, making the dollar sign for the start state
			FollowSet[main_rule].push_back("$");
		TDData[main_rule] = vector<vector<string> > ();

		vector<string> toInsert = vector<string> ();
		vector<string>::iterator itvec;
		for (int i = 0; i < vec.size(); i++) {
			string value = vec[i];
			if (value.compare("|") == 0) {
				TDData[main_rule].push_back(toInsert);
				toInsert.clear();
			} else
				toInsert.push_back(value);
		}
		TDData[main_rule].push_back(toInsert); // this is for when we reach the end without "|"
		toInsert.clear(); // this doesn't really need to be done.
	}
}

void Parser::printVector(vector<string> &vec) {
	if (vec.size() == 0)
		printf("EMPTY \n");
	else {
		for (int i = 0; i < vec.size(); i++) {
			printf("%s ", vec[i].c_str());
		}
		printf("\n");
	}
}

void Parser::printVector(vector<vector<string> > &vec) {
	if (vec.size() == 0)
		printf("EMPTY \n");
	else {

		for (int i = 0; i < vec.size(); i++) {
			if (i != 0)
				printf(" | ");
			for (int j = 0; j < vec[i].size(); j++) {
				printf("%s ", vec[i][j].c_str());
			}

		}
		printf("\n");

	}
}
void Parser::print2DMap(MapType &themap) {
	for (MapType::const_iterator it = themap.begin(); it != themap.end(); ++it) {

		string main_rule = it->first;
		vector<string> vec = it->second;
		printf("%s -> ", main_rule.c_str());
		printVector(vec);

	}

}
void Parser::print3DMap(ThreeDMapType &TheData) {
	printf("\n");
	// this is for printing everything out;
	for (ThreeDMapType::iterator it = TheData.begin(); it != TheData.end(); ++it) {
		string main_rule = it->first;
		vector<vector<string> > vec = it->second;
		printf("%s -> ", main_rule.c_str());
		printVector(vec);

	}

}

void Parser::eliminateSpaces(vector<string> &vec) {
	for (vector<string>::iterator it = vec.begin(); it < vec.end(); it++) {
		if ((*it).compare(" ") == 0)
			it = vec.erase(it);
	}
}

bool Parser::isTerminal(string toTest) {
	//	listOfTokens.push_back("ε");

	if (toTest.compare("ε") == 0)
		return true;
	for (vector<string>::iterator it = listOfTokens.begin(); it
			< listOfTokens.end(); it++) {
		if ((*it).compare(toTest) == 0)
			return true;
	}

	return false;
}

